package demo2;

import java.util.*;

public class Solution {

    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;

        int ret = Integer.MAX_VALUE, t = 0;
        for(int left = 0, right = 0; right < n; right++){
            t += nums[right];
            while(t >= target){
                ret = Math.min(ret, right - left + 1);
                t -= nums[left++];
            }
        }
        return ret == Integer.MAX_VALUE ? 0 : ret;
    }

    public String shortestBeautifulSubstring(String s, int k) {
        if(s.replace("0", "").length() < k){ return "";}
        int n = s.length();

        for(int size = k; ; size++){
            String ret = "";
            for(int i = size; i <= n; i++){
                String t = s.substring(i - size, i);
                if((ret.isEmpty() || t.compareTo(ret) < 0) && t.replace("0", "").length() == k){
                    ret = t;
                }
            }
            if(!ret.isEmpty()){
                return ret;
            }
        }
    }

    public int balancedString(String s) {
        int n = s.length();
        int[] hash = new int['X'];
        for(int i = 0; i < n; i++){
            hash[s.charAt(i)]++;
        }

        int ret = n, m = n / 4;
        if(hash['Q'] == m && hash['W'] == m && hash['E'] == m && hash['R'] == m) { return 0;}

        for(int left = 0, right = 0; right < n; right++){
            hash[s.charAt(right)]--;

            while(hash['Q'] <= m && hash['W'] <= m && hash['E'] <= m && hash['R'] <= m){
                ret = Math.min(ret, right - left + 1);
                hash[s.charAt(left++)]++;
            }
        }
        return ret;
    }

    public int minSizeSubarray(int[] nums, int target) {
        long total = 0;
        for(int x : nums) { total += x;}
        int n = nums.length;
        int ret = Integer.MAX_VALUE;
        long sum = 0;

        for(int left = 0, right = 0; right < n * 2; right++){
            sum += nums[right % n];

            while(sum > target % total){
                sum -= nums[left++ % n];
            }

            if(sum == target % total){
                ret = Math.min(ret, right - left + 1);
            }
        }
        return ret == Integer.MAX_VALUE ? -1 : ret + (int)(target / total) * n;
    }

    public String minWindow(String s, String t) {
        int n = s.length(), m = t.length();
        int[] h1 = new int[128];
        for(int i = 0; i < m; i++){
            h1[t.charAt(i)]++;
        }

        int begin = -1 ,len = Integer.MAX_VALUE;
        int[] h2 = new int[128];
        for(int left = 0, right = 0, count = 0; right <n; right++){
            char in = s.charAt(right);
            h2[in]++;
            if(h2[in] <= h1[in]) { count++;}

            while(count == m){
                if(right - left + 1 < len){
                    begin = left;
                    len = right - left + 1;
                }

                char out = s.charAt(left);
                if(h2[out] <= h1[out]) { count--;}
                h2[out]--;
                left++;
            }
        }

        return begin == -1 ? "" : s.substring(begin, begin + len);
    }
}
